//题目:
// 给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
// 请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
// 如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
// 军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
//代码:
class Solution 
{
public:
    struct compare
    {
        bool operator()(const pair<int,int> pir1,const pair<int,int> pir2)
        {
            return pir1.second<pir2.second || (pir1.second==pir2.second && pir1.first<pir2.first);
            //先对second建大根堆，排降序;若second相同,则对first建大根堆，排降序
        }
    };
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) 
    {
        //1.用优先级队列记录每行有几个军人（1）
        priority_queue<pair<int,int>,vector<pair<int,int>>,compare> heap;//key是第i行，value代表第i行的军人数量
        //2.遍历mat，并对heap元素插入
        for(int i=0;i<mat.size();i++)
        {
            int count=0;//记录第i行有几个军人
            for(int j=0;j<mat[i].size();j++)
            {
                if(mat[i][j]==1)count++;
                else break;
            }
            heap.push(make_pair(i,count));
            if(heap.size()>k)heap.pop();//把大的丢掉，小的保留，最后剩下的k个就是最弱的k行
        }
        //3.提取结果，注意：此时heap中的元素的降序
        vector<int> ret(k);
        for(int i=k-1;i>=0;i--)
        {
            ret[i]=heap.top().first;
            heap.pop();
        }
        return ret;
    }
};